import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/22 9:49
 * @description SG定理 记忆化搜索 + 状态DP
 */
public class Solution {
    public static void main(String[] args) {

    }

    /**
     * 备忘录
     */
    Map<Integer, Boolean> memo = new HashMap<>();
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) {
            // 所有数都被选完，但是无法达到期望和，两人都无法获胜
            return false;
        }
        return dfs(maxChoosableInteger, 0, desiredTotal, 0);
    }

    /**
     * 状态DP递归函数
     * @param max maxChoosableInteger
     * @param usedNumbers 用一个整数表示，从低位到高位，第i位为1，则表示数字i已经被使用，为0则表示数字i未被使用。
     * @param desiredTotal 期望和
     * @param currentTotal 目前和
     * @return boolean
     */
    public boolean dfs(int max, int usedNumbers, int desiredTotal, int currentTotal) {
        if (!memo.containsKey(usedNumbers)) {
            boolean res = false;
            for (int i = 0; i < max; i++) {
                if (((usedNumbers >> i) & 1) == 0) {
                    // i + 1是因为选择的数范围 [1，max]
                    if (i + 1 + currentTotal >= desiredTotal) {
                        res = true;
                        break;
                    }
                    if (!dfs(max, usedNumbers | (1 << i), desiredTotal, currentTotal + i + 1)) {
                        res = true;
                        break;
                    }
                }
            }
            memo.put(usedNumbers, res);
        }
        return memo.get(usedNumbers);
    }
}
